Field
This disclosure relates to asynchronous digital logic circuits.
Description of the Related Art
In this patent, the term “processor” means a digital circuit that performs some sequence of operations. A processor may typically, but not necessarily, execute stored instructions to accomplish its assigned function. Processors that typically execute stored instructions include microprocessors, microcontrollers, digital signal processors, and coprocessors. Processors that do not execute stored instructions include single-purpose processors such as encryption engines and fast Fourier transform engines. The sequence of operations performed by such engines may be controlled, for example, by a hardware state machine rather than stored instructions.
Most digital processors in use today are synchronous, which is to say various elements within the digital processor operate synchronously in response to a common clock signal. The power consumption of a synchronous processor depends on the complexity of the processor (i.e. the number of gates and other functional elements), the clock rate, and the operating voltage. In general, higher operating speed requires higher operating voltage.
Asynchronous, or self-timed, processor circuits do not operate from a common clock signal, such that the delay of a self-timed processor is determined solely by the cumulative delay of the gates and other logic elements within the self-timed processor. Self-timed processors are typically operated in a cyclic manner. A cycle is initiated when input data is provided to the processor. The processor then performs some operation upon the input data, with the time required to perform the operation determined by the accumulated delays of the logic circuits within the processor. When the operation is complete and all of the outputs of the processor have assumed their final values, a feedback or acknowledge signal may be generated to indicate completion of the current cycle and readiness to begin the next cycle.
Null convention logic (NCL) is a delay-insensitive logic paradigm in which each Boolean variable has three defined states: “True”, “False”, and “null”, where the null state indicates that a valid value is not yet available. In this patent, the term “valid” means a Boolean variable is in either the True or False states. NCL processors typically employ a combination of dual-rail logic and threshold gates.
Dual-rail logic is a form of NCL that uses two signals or rails, each of which has two possible values (1 or 0), to represent each Boolean variable. In this patent, the two signals will be referred to as the “true” and “false” rail. For a Boolean variable “A”, the two rails will be designated as AT, and AF. A Boolean “1” or “true” state is represented by AT=1, AF=0, and a Boolean “0” or “false” state is represented by AT=0, AF=1. Either of these are “valid” or “valid states”. The null state is represented by AT=AF=0. The state AT=AF=1 is forbidden. Another form of NCL uses four rails or signals to collectively represent two Boolean variables. In this patent, the term “multi-rail” encompasses both dual-rail and four-rail implementations of NCL. The term “single-rail” means a conventional binary value.
An NCL processor is typically operated in a cyclical manner. All of the inputs to an NCL processor are initially set to the null state, which then propagates through the processor until all of the outputs of the processor assume the null state. This is considered the “null phase” of the processing cycle. When all of the outputs of the processor are in the null state, the processor sets an acknowledge signal output to a first state (commonly called “request for data”) indicating the processor is ready for new data. The inputs to the processor are then set to valid states, which then propagate through the processor until all of the outputs also assume valid states. This is considered the “data phase” of the processing cycle. When all of the outputs have assumed valid states, the cycle is complete and the acknowledge signal is set to a second state (commonly called “request for hull”) to initiate the next cycle. An NCL processor may be divided into multiple functional blocks typically arranged as a pipeline. In this case, each functional block may generate a respective acknowledge signal that is provided to the predecessor functional block in the pipeline.
Threshold gates are a type of logic gate, where “gate” is defined as a logic circuit having two or more inputs combined into a single output. The output of a threshold gate is set to 0 only when all of its inputs are 0. The output of a threshold gate is set to 1 when a predetermined combination of inputs are all 1. With other combinations of inputs, the output of the threshold gate retains its previous value. A nomenclature commonly used to describe some types of threshold gates is “THmn”, where n and m are integers between one and four. “n” is the number of inputs to the gate, and “m” is the number of inputs that must be 1 for the output of the gate to switch to 1.
The use of only threshold gates for combinatorial logic provides both “input completeness” and “null completeness.” Input completeness means all of the outputs of a block of combinatorial logic can be in valid states only if all of the inputs and all of the interval Boolean values within the block are also in valid states. Null completeness means all of the outputs can be in the null state only if all inputs and all of the interval Boolean values within the block are in the “null” state. The completion of the data phase and the null phase of NCL processor implemented with multi-rail logic and only threshold gates can be unambiguously detected. Thus the results provided by an NCL processor implemented with multi-rail logic and only threshold gates are insensitive to the propagation delays of the individual gates within the processor.
Throughout this description, elements appearing in figures are assigned three-digit reference designators, where the most significant digit is the figure number where the element is introduced and the two least significant digits are specific to the element. An element that is not described in conjunction with a figure may be presumed to have the same characteristics and function as a previously-described element having the same reference designator.